package algorithm;

public class leetcode_0042_2 {
    public int trap(int[] height) {
        int len=height.length;
        int[] left=new int[len];
        int[] right=new int[len];
        int capacity=0;
        left[0]=height[0];
        for(int i=1;i<len;++i){
            left[i]=(height[i-1]>left[i-1])?height[i-1]:left[i-1];
        }
        right[len-1]=height[len-1];
        for(int i=len-2;i>=0;--i){
            right[i]=(height[i+1]>right[i+1])?height[i+1]:right[i+1];
        }
        for(int i=1;i<len-1;++i){
            int current=((left[i]>right[i])?right[i]:left[i])-height[i];
            if(current>0) capacity+=current;
        }
        return capacity;
    }
}
